package com.lw.leetcode.hash.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * map
 * 332. 重新安排行程
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/19 17:51
 */
public class FindItinerary {


    public static void main(String[] args) {
        FindItinerary test = new FindItinerary();
        List<List<String>> lists = new ArrayList<>();

        //输出：["JFK","MUC","LHR","SFO","SJC"]
//        lists.add(Arrays.asList("MUC", "LHR"));
//        lists.add(Arrays.asList("JFK","MUC"));
//        lists.add(Arrays.asList("SFO","SJC"));
//        lists.add(Arrays.asList("LHR","SFO"));


        // [JFK, NRT, JFK, KUL]
        lists.add(Arrays.asList("JFK", "KUL"));
        lists.add(Arrays.asList("JFK", "NRT"));
        lists.add(Arrays.asList("NRT", "JFK"));

        List<String> itinerary = test.findItinerary(lists);
        System.out.println(itinerary);
    }

    private Map<String, List<String>> map;
    private int length;
    private List<String> values;

    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, List<String>> map = new HashMap<>();
        for (List<String> ticket : tickets) {
            String a = ticket.get(0);
            String b = ticket.get(1);
            List<String> list = map.computeIfAbsent(a, v -> new ArrayList<>());
            list.add(b);
        }
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            Collections.sort(entry.getValue());
        }
        this.length = tickets.size();
        this.map = map;
        this.values = new ArrayList<>(length + 1);

        find("JFK", 0);
        values.add("JFK");
        List<String> list = new ArrayList<>(length + 1);
        for (int a = length; a >= 0; a--) {
            list.add(values.get(a));
        }
        return list;
    }

    private boolean find(String key, int count) {
        if (count == length) {
            return true;
        }
        List<String> list = map.get(key);

        if (list == null) {
            return false;
        }
        int size = list.size();
        for (int i = 0; i < size; i++) {
            String s = list.get(i);
            if ("".equals(s)) {
                continue;
            }
            list.set(i, "");
            boolean b = find(s, count + 1);
            list.set(i, s);
            if (b) {
                values.add(s);
                return b;
            }
        }
        return false;
    }

}
